﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    class PigeonHole
    {
        public void Sort()
        {

            //            Pigeonhole sort
            var pigeonHole = new int[10];//10个位置

            var A = new int[] { 6, 6, 2, 2, 2, 4, 1, 1, 1, 5, 5, 5, 5, 9 };//待排序数组

            foreach (var item in A)
            {

                pigeonHole[item]++;//如pigeonHole[6]++会执行两次,结果为2

            }

            //鸽巢索引:0 1 2 3 4 5 6 7 8 9
            //索引次数:0 3 3 0 1 4 2 0 0 1

            //顺序输出

            for (int i = 0; i < pigeonHole.Length; i++)//索引i就是值
            {

                //pigeonHole[i]处的值是数字i出现的次数

                //如6出现了两次,那么pigeonHole[6] = 2

                //0没出现,那么pigeonHole[0] = 0,表示待排数组里没有这个值:0

                for (int j = 0; j < pigeonHole[i]; j++)//i出现就次就输出几个
                {

                    Console.WriteLine(i);//1,1,1,2,2,2,4,5,5,5,5,6,6,9

                }

            }
        }
    }
}
